//
//  HashTable.hpp
//  hashtable
//
//  Created by chenyh on 2021/2/5.
//

#ifndef HashTable_hpp
#define HashTable_hpp

#include <iostream>
template<typename DataType>
class HashTable
{
public:
    HashTable(int size)
    {
        maxSize = size;
        count   = 0;
        elements = new DataType[size];
        if (elements == NULL) {
            exit(1);
        }
        for (int i = 0; i < size; i++) {
            elements[i] = NULL;
        }
    }
    ~HashTable()
    {
        delete [] elements;
    }
    //散列函数---除留取余，p为根据关键字集合设定的值
    int hash(DataType value);
    //查找函数，返回所查找元素的地址
    int searchHash(DataType value);
    
    DataType getData(int i)
    {
        if (i < 0) {
            std::cout<<"所引致错误！必须为正整数"<<std::endl;
        }
        return elements[i - 1];
        
    }
    
    bool insertHash(DataType value);
    
private:
    int maxSize;
    int count;
    DataType *elements;
};

//哈希函数
template <typename  DataType>
int HashTable<DataType>:: hash(DataType value) {
    return value % maxSize;   //采用除留取余
}
/**
 下面的代码利用除留取余法设计散列函数，然后用开放定址法处理冲突，用线性探测 的方式来寻找空白地址。仔细观察可以看出，散列表是一种为查询所设计的数据结构，查 找是它的主要功能，至于插入、删除等操作，都是需要以查找为基础的，如上面代码中的 在空白地址中插入元素，就是散列表的插入操作的一个简单实现，具体的插入、删除操作， 这里不再赘述，请读者自己尝试一下。
 */
template <typename  DataType>
int HashTable<DataType>:: searchHash(DataType value) {
    int p = hash(value);
    if (elements[p] == value) {
        return p;
    }
    
    int rp = (p+1) % maxSize;   //线性探测法处理冲突，选取d=1；
    while (rp != p) { //rp==p时说明没有找到所需函数
        if (elements[rp] == value) {
            return rp;
        }
        if (elements[rp] == NULL) { //找到空白地址
            break;
        }
        rp = (rp+1) % maxSize; //循环使用线性探测发找空白地址
    }
    if (rp == p) {
        return -1;
    }
    else
    {
        elements[rp] = value; //在空白地址上插入此元素
        return rp;
    }

}

template <typename  DataType>
bool HashTable<DataType>:: insertHash(DataType value) {
    int pos = searchHash(value); //查找指定元素，看看散列表中是否已经存在
    if (pos < 0) { //查找失败且表满
        return false;
    }
    else if(elements[pos] == value)//有重复元素
    {
        std::cout<<"重复的元素!"<<std::endl;
        return false;
    }
    else
    {
        elements[pos] = value; //在空白地址插入元素
        return true;
    }
        
}
#endif /* HashTable_hpp */
